package com.zou.dataStruct.Graph.Linked;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

//邻接表构造
public class Graph {
    private int n;
    private HeadNode head[];

    public Graph(){}

    public Graph(String str) {
        this.n = str.length();
        this.head = new HeadNode[n];
        for(int i=0;i<head.length;i++){
            head[i] = new HeadNode(str.charAt(i));
        }
    }

    //头插法 p->sn->s(n-1)->....->s2->s1
    //用栈就头插法吧
    /**
     * @param i:头结点索引
     * @param p:要插入的边结点
     */
    public void insertHead(int i,EdgeNode p){
        p.setNext(head[i].getFirst());
        head[i].setFirst(p);
    }

    //2.尾插法:p->s1->s2->.....->s(n-1)->sn

    /**
     * @param i:头结点索引
     * @param p:要插入的边结点
     */
    public void insertail(int i,EdgeNode p){
        if(head[i].getFirst()==null){
            head[i].setFirst(p);
        }else{
            EdgeNode e = head[i].getFirst();
            while(e.getNext()!=null){
                e = e.getNext();
            }
            e.setNext(p);
        }
    }

    //输出图
    public void printG(){
        for (int i = 0; i < n; i++) {
            System.out.print(head[i].getCh() + "->");
            EdgeNode e = head[i].getFirst();
            while (e != null) {
                System.out.print(head[e.getData()].getCh() + "->");
                e = e.getNext();
            }
            System.out.println();
        }
    }

    public void DFS(int i){
        boolean b[] = new boolean[n];
        Stack<Integer> stack = new Stack<>();
        stack.push(i);
        b[i] = true;
        while(!stack.isEmpty()){
            i = stack.pop();
            System.out.print(head[i].getCh()+"->");
            EdgeNode e = head[i].getFirst();
            while(e!=null){
                if(b[e.getData()]==false){
                    stack.push(e.getData());
                    b[e.getData()] = true;
                }
                e = e.getNext();
            }
        }
    }

    public void BFS(int start){
        boolean []b = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        b[start] = true;
        while(!queue.isEmpty()){
            int e = queue.poll();
            System.out.print(head[e].getCh()+"->");
            EdgeNode p = head[e].getFirst();
            while(p!=null){
                if(b[p.getData()]==false){
                    queue.offer(p.getData());
                    b[p.getData()] = true;
                }
                p = p.getNext();
            }
        }
    }

}
